package sort;

/**
 * 排序一个链表（升序）
 * 使用归并排序，排序链表
 * @author HuWLin
 *
 * */


public class LinkedListSort {
    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }

    public ListNode sortList(ListNode head,ListNode tail) {
        if(head == null) {
            return null;
        }
        //若当前头结点的下一个结点就是尾结点，就说明只有两个数据
        if(head.next == tail) {
            head.next = null;
            return head;
        }
        //这里使用快慢指针将中间节点找出来
        ListNode slow = head,fast = head;
        while(fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if(fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        //left返回的数据是head结点到mid结点不包括mid，right是mid到tail不包括tail
        ListNode left = sortList(head,mid);
        ListNode right = sortList(mid,tail);
        //进行归并
        return merge(left,right);
    }

    public ListNode merge(ListNode left,ListNode right) {
        //用于返回的头节点，不存数据
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        //同时满足都不为空
        while(left != null && right != null) {
            //判断小的在前，大的在后
            if(left.val < right.val) {
                tmp.next = left;
                left = left.next;
            }else {
                tmp.next = right;
                right = right.next;
            }
            tmp = tmp.next;
        }
        //只有三种情况，left和right一样长，此情况啥也不用做
        //left多一个数据
        if(left != null) {
            tmp.next = left;
        }else if(right != null) { //right多一个数据
            tmp.next = right;
        }
        //此时返回的数据已经是排序好的了
        return head.next;
    }
}

